package leetcode.code1803;

import java.util.HashMap;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int n = Integer.toBinaryString(100000).length();

	public int countPairs(int[] nums, int low, int high) {
		Node root = new Node();
		int h = high;
		int l = low - 1;
		int ans = 0;
		for (int num : nums) {
			ans += find(root, num, h) - find(root, num, l);
			add(root, num);
		}
		return ans;
	}

	private void add(Node root, int num) {
		Node node = root;
		for (int i = n; i >= 0; i--) {
			int cur = (num >> i) & 1;
			node = node.computeIfAbsent(cur, k -> new Node());
			node.cnt++;
		}

	}

	private int find(Node root, int num, int range) {
		Node node = root;
		int ans = 0;
		for (int i = n; i >= 0 && node != null; i--) {
			int cur = (num >> i) & 1;
			int r = (range >> i) & 1;
			if (r == 1) {
				ans += node.getOrDefault(cur, new Node()).cnt;
			}
			node = node.get(cur ^ r);
		}
		if (node != null) {
			ans += node.cnt;
		}
		return ans;
	}

	class Node extends HashMap<Integer, Node> {
		int cnt;
	}

	@Override
	public void debug4() {
		H.compare(6, this.countPairs(H.str2array3("[1,4,2,7]"), 2, 6));
		H.compare(8, this.countPairs(H.str2array3("[9,8,4,2,1]"), 5, 14));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		System.out.println(Integer.toBinaryString(2 * 10000));
	
		
	}

}
